import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * 
 * 子图同构
 * 
 * 描述：
给定两个有向图，判断它们是否是同构的。如果一个图的节点可以一一映射到另一个图的节点，并且映射后的图与原图结构相同，则这两个图是同构的。


输入: 两个图的邻接表表示
图1: [[1,2],[2,3],[3,4]]
图2: [[1,2],[2,3],[3,4]]
输出: true

 */
public class 子图同构 {
    
    public static void main(String[] args) {
        

        Graph graph1 = new Graph();
        GraphNode node1 = new GraphNode(1);
        GraphNode node2 = new GraphNode(2);
        GraphNode node3 = new GraphNode(3);
        node1.neighbors.add(node2);
        node2.neighbors.add(node3);
        graph1.addNode(node1);
        graph1.addNode(node2);
        graph1.addNode(node3);

        // 创建图 2
        Graph graph2 = new Graph();
        GraphNode node4 = new GraphNode(4);
        GraphNode node5 = new GraphNode(5);
        GraphNode node6 = new GraphNode(6);
        GraphNode node7 = new GraphNode(7);
        node4.neighbors.add(node5);
        node5.neighbors.add(node6);
        node6.neighbors.add(node7);
        graph2.addNode(node4);
        graph2.addNode(node5);
        graph2.addNode(node6);
        graph2.addNode(node7);

        boolean isomorphic = isSubgraphIsomorphic(graph1, graph2);
        System.out.println("图 1 和图 2 是否同构：" + isomorphic);

    }

    private static boolean isSubgraphIsomorphic(Graph graph1, Graph graph2) {
        if (graph1.nodes.size() > graph2.nodes.size()) {
            return false;
        }
        //boolean[] visited = new boolean[graph2.nodes.size()];
        return findIsomorphism(graph1.nodes.get(0), graph2.nodes.get(0), graph1, graph2);
    }

    private static boolean findIsomorphism(GraphNode node1, GraphNode node2, Graph graph1, Graph graph2) {
        if (node1.label!= node2.label) {
            return false;
        }

        List<GraphNode> neighbors1 = node1.neighbors;
        List<GraphNode> neighbors2 = node2.neighbors;
        if (neighbors1.size()!= neighbors2.size()) {
            return false;
        }
        for (GraphNode neighbor1 : neighbors1) {
            boolean found = false;
            for (int i = 0; i < neighbors2.size(); i++) {
                if (neighbors2.get(i).label == neighbor1.label && findIsomorphism(neighbor1, neighbors2.get(i), graph1, graph2)) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                return false;
            }
        }
        return true;
    }

    private static class GraphNode {
        int label;
        List<GraphNode> neighbors;

        public GraphNode(int label) {
            this.label = label;
            neighbors = new ArrayList<>();
        }
    }

    private static class Graph {
        List<GraphNode> nodes;
    
        public Graph() {
            nodes = new ArrayList<>();
        }
    
        public void addNode(GraphNode node) {
            nodes.add(node);
        }
    }
}
